#ifndef _AD_CONSTRUCT_H_
#define _AD_CONSTRUCT_H_

#include "grate_constants.h"
#include "words_queue.h"
#include "dfa.h"
#include "input_data.h"
#include "grate_config.h"

// Main function, called to construct the AD using WORDS_QUEUE, and store AD in the trie DFA
// Returns the maximal number of symbols that were present in the queue at one moment
i64 construct_antidictionary(grate_config & CONFIG, input_data & INPUT, words_queue * WORDS_QUEUE, dfa * DFA);

// Returns the miminal length of forbidden word where plen is the length of its root
inline int get_length(int plen, const input_data & INPUT);

// Get maximal length of Y in the forbidden word XYX
inline int get_y(int x, const input_data & INPUT);

// Gets minimal length of root XY in forbidden word XYX
inline int get_root(int x, const input_data & INPUT);

// Precalcs values of getLength, getY and badRoots
void precalc_arrays(const input_data & INPUT);

// Hadles root stored in cword and adds forbidden word constructed from it if necessary
// This root will still be bad after writing down still_bad more letters (if it is -1, it can be good)
void handle_root(char* cword, int clen, char * cpans, int cplen, int badness, dfa * DFA, input_data & INPUT);

void handle_root_dumb(char* cword, int clen, char * cpans, int cplen, int badness, dfa * DFA, input_data & INPUT);

// Check all prefixes of cword starting from cword[0..slen] to cword[0..clen-1]
// Checks only root lengths for which there are no words in AD
// Returns the number of the first prefix which is bad
int has_bad_prefix_dumb(const char* cword, int clen, int slen, input_data & INPUT);

inline int get_lcp_dumb(const char * cword, int clen, int i, int j);

// Builds suffix array and lcp array for a given length (from the previous one)
void rebuild_suffix_array(const char * cword, int cwlen);

void run_dfs(char * cword, int cwlen, char * cpans, int cplen, int badness, dfa * DFA, input_data & INPUT);

bool can_append_letter_dumb(const char * cword, int clen, char letter, input_data & INPUT);
bool can_append_letter(const char * cword, int clen, char letter, input_data & INPUT);

#endif